#pragma once

#include "utility.h"
#include "AVLTree.h"
#include "RBTree.h"
#include <initializer_list>

namespace qyc
{
	template<class K, class Compare = less<K>>
	class set
	{
		struct SetKeyOfValue
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		typedef RBTree<K, K, SetKeyOfValue, Compare> tree_type;
		typedef set<K, Compare> self;
	public:
		typedef typename tree_type::const_iterator iterator;
		typedef typename tree_type::const_iterator const_iterator;
		typedef typename tree_type::reverse_iterator reverse_iterator;
		typedef typename tree_type::const_reverse_iterator const_reverse_iterator;

		set() = default;
		template<class InputIterator>
		set(InputIterator first, InputIterator last)
		{
			_tree.insert_range(first, last);
		}
		set(std::initializer_list<K> _Ilist)
		{
			_tree.insert_range(_Ilist.begin(), _Ilist.end());
		}

		iterator begin()
		{
			return _tree.begin();
		}
		iterator end()
		{
			return _tree.end();
		}
		const_iterator begin() const
		{
			return _tree.begin();
		}
		const_iterator end() const
		{
			return _tree.end();
		}
		reverse_iterator rbegin()
		{
			return _tree.rbegin();
		}
		reverse_iterator rend()
		{
			return _tree.rend();
		}
		const_reverse_iterator rbegin() const
		{
			return _tree.rbegin();
		}
		const_reverse_iterator rend() const
		{
			return _tree.rend();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return emplace(key);
		}
		pair<iterator, bool> insert(K&& key)
		{
			return emplace(qyc::forward<K>(key));
		}
		template <class... Args>
		pair<iterator, bool> emplace(Args&&... args)
		{
			pair<typename tree_type::iterator, bool> ret = _tree.emplace(args...);
			return pair<iterator, bool>(ret.first, ret.second);
		}
		template<class InputIterator>
		void insert(InputIterator first, InputIterator last)
		{
			_tree.insert_range(first, last);
		}
		void erase(const K& key)
		{
			_tree.erase(key);
		}

		iterator find(const K& key)
		{
			return _tree.find(key);
		}
		const_iterator find(const K& key) const
		{
			return _tree.find(key);
		}

		void clear()
		{
			_tree.clear();
		}
		bool empty() const
		{
			return _tree.empty();
		}
		size_t size() const
		{
			return _tree.size();
		}
		void swap(self& des)
		{
			_tree.swap(des._tree);
		}
	private:
		tree_type _tree;
	};

	template<class K, class Compare = less<K>>
	class multiset
	{
		struct multiSetKeyOfValue
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		typedef RBTree<K, K, multiSetKeyOfValue, Compare> tree_type;
		typedef multiset<K, Compare> self;
	public:
		typedef typename tree_type::const_iterator iterator;
		typedef typename tree_type::const_iterator const_iterator;
		typedef typename tree_type::reverse_iterator reverse_iterator;
		typedef typename tree_type::const_reverse_iterator const_reverse_iterator;

		multiset() = default;
		template<class InputIterator>
		multiset(InputIterator first, InputIterator last)
		{
			_tree.insert_equal_range(first, last);
		}
		multiset(std::initializer_list<K> _Ilist)
		{
			_tree.insert_equal_range(_Ilist.begin(), _Ilist.end());
		}

		iterator begin()
		{
			return _tree.begin();
		}
		iterator end()
		{
			return _tree.end();
		}
		const_iterator begin() const
		{
			return _tree.begin();
		}
		const_iterator end() const
		{
			return _tree.end();
		}
		reverse_iterator rbegin()
		{
			return _tree.rbegin();
		}
		reverse_iterator rend()
		{
			return _tree.rend();
		}
		const_reverse_iterator rbegin() const
		{
			return _tree.rbegin();
		}
		const_reverse_iterator rend() const
		{
			return _tree.rend();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return emplace(key);
		}
		pair<iterator, bool> insert(K&& key)
		{
			return emplace(qyc::forward<K>(key));
		}
		template <class... Args>
		pair<iterator, bool> emplace(Args&&... args)
		{
			pair<typename tree_type::iterator, bool> ret =  _tree.emplace_equal(args...);
			return pair<iterator, bool>(ret.first, ret.second);
		}
		template<class InputIterator>
		void insert(InputIterator first, InputIterator last)
		{
			_tree.insert_equal_range(first, last);
		}
		void erase(const K& key)
		{
			_tree.erase(key);
		}

		iterator find(const K& key)
		{
			return _tree.find(key);
		}
		const_iterator find(const K& key) const
		{
			return _tree.find(key);
		}

		void clear()
		{
			_tree.clear();
		}
		bool empty() const
		{
			return _tree.empty();
		}
		size_t size() const
		{
			return _tree.size();
		}
		void swap(self& des)
		{
			_tree.swap(des._tree);
		}
	private:
		tree_type _tree;
	};
}